package com.wang.violentrecursion;

/**
 * @Author: along
 * @Create: 2021/5/4
 * @Description:玩家A和B在给定一个包含纸牌数组边界取牌，取到牌的和大者获胜，返回获胜者分数
 */
public class Demo06_CardInline {

    public static int win1(int arr[]) {
        //如果没有牌 直接返回0
        if(arr == null || arr.length ==0 ) {
            return 0;
        }
        //先手获取的分数 后手获取的分数 比较 大的即获胜 返回
        return Math.max(
                f(arr, 0, arr.length - 1), //先手获得的分数
                s(arr, 0, arr.length - 1));//后手获得的分数
    }
    //先手拿
    public static int f(int arr[], int L, int R) {
        //如果只有一张牌，先手直接拿，然后返回
        if(L == R) {
            return arr[L];
        }
        return Math.max(
                arr[L] + s(arr,L + 1, R), //先手拿L位置，那么下一次（[L+1, R] 就变为后手拿
                arr[R] + s(arr, L, R - 1));//先手拿位置，那么下一次（[L, R-1] 就变为后手拿
    }
    //后手拿
    public static int s(int arr[], int L, int R) {
        //如果只剩一张牌，且自己是后手，不归我拿，则返回0
        if(L == R) {
            return 0;
        }
        //后手拿是在对手先手拿过的情况下，所以为最坏情况
        return Math.min(
                f(arr, L + 1, R), //对手拿arr[L]剩下的后续
                f(arr, L, R - 1));//对手拿arr[R]剩下的后续
    }

    //动态规划
    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] f = new int[N][N];
        int[][] s = new int[N][N];

        for (int j = 0; j < N; j++) {
            f[j][j] = arr[j];//对角线的值等于arr[j]
            //s[j][j] = 0; //初始化默认为0
            for (int i = j - 1; i >= 0; i--) {
                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
            }
        }
        return Math.max(f[0][N - 1], s[0][N - 1]);
    }

    public static void main(String[] args) {
        int[] arr = { 1, 9, 1, 15, 5, 10 };
        System.out.println(win1(arr));
        System.out.println(win2(arr));
    }

}
